package binaryTreePaths;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Solution {
    public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;

          TreeNode() {
          }

          TreeNode(int val) {
              this.val = val;
          }

          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<Integer> stack = new LinkedList<>();
        List<String> ans = new ArrayList<>();
        dfs(ans,root,new LinkedList<>());
        return ans;
    }
    private void dfs(List<String> ans,TreeNode root,LinkedList<Integer> list) {
        list.add(root.val);
        if(root.left == null&&root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size()-1; i++) {
                sb.append(list.get(i)).append("->");
            }
            sb.append(list.get(list.size()-1));
            ans.add(sb.toString());
        }
        if(root.left!=null) {
            dfs(ans,root.left,list);
            list.removeLast();
        }
        if(root.right!=null) {
            dfs(ans,root.right,list);
            list.removeLast();
        }
    }

}